1. Field of the Invention
The present invention relates to a residue computing system for finding residues of numbers with respect to a given modulus, and particularly to a residue computing system which is capable of computing the residues at a high speed with small memory capacity.
2. Description of the Prior Art
In recent years, the use of cryptosystems to protect information against illegal access, wiretapping and alteration has been developed. Among various encryption techniques, a public key cryptosystem is advantageous because it can conceal the information and verify the writer of a message, i.e., it has a digital signature function.
The most promising public key cryptosystem to be used for IC cards, etc., may be an RSA public key cryptosystem, which was proposed by Rivest, Shamir and Adleman.
In the RSA public key cryptosystem, encryption and decryption are executed with the following algorithms:
C=M.sup.e mod n (encryption) PA1 M=C.sup.d mod n (decryption) PA1 (a) storing, in a memory means, at most a.sup.b different residues with respect to said modulus N, where b is a predetermined number; PA1 (b) partitioning said number M on a shift register means into a b-digit block X obtained by a latch means for separating b most significant digits of said number M, and a remaining portion Z of (m-b) digits; PA1 (c) finding a residue Rx corresponding to said block X with respect to said modulus N by looking up in said memory means; PA1 (d) aligning a least significant digit of said residue Rx with a q-th most significant digit of said remaining portion Z; PA1 (e) adding said residue Rx and said remaining portion Z as aligned in step (d) to obtain a number Rq: and PA1 (f) taking said number Rq as a residue R of said number M when said number Rq has not more than q digits, but otherwise repeating steps (b) to (f) with said number Rq replacing said number M. PA1 shift register means for temporarily holding said number M; PA1 memory means for storing at most a.sup.b different residues with respect to said modulus N, where b is a predetermined number; PA1 latch means for partitioning said number M in a shift register means into a b-digit block X obtained by separating b most significant digits of said number M, and a remaining portion Z of (m-b) digits; PA1 means for finding a residue Rx corresponding to said block X with respect to said modulus N by looking up in said memory means; PA1 means for aligning a least significant digit of said residue Rx with a q-th most significant digit of said remaining portion Z; PA1 adder means for obtaining a number Rq by adding said residue Rx and said remaining portion Z as aligned by said aligning means; PA1 means for determing whether said number Rq has more than q digits; PA1 means for replacing said number M in said shift register means by said number Rx when said number Rx has more than q digits. PA1 (a) storing, in a memory means, precomputed s-digit residues of at most k*a.sup.b/k different numbers with respect to said modulus N, where s, b and k are predetermined numbers; PA1 (b) partitioning said number M on a shift register means into a block X of b digits obtained by a latch means for separating b most significant digits of said number M, and a remaining portion Z of (q-b) digits, where b is a number equal to s times k: PA1 (c) partitioning said block X into k sub-blocks Xi(i=1, . . . , k), each of s digits; PA1 (d) finding residues Ri corresponding to said sub-blocks Xi with respect to said modulus N by looking up said memory means; PA1 (e) aligning least significant digits of the residues Ri with the q-th most significant digit of said remaining portion Z; PA1 (f) adding said residues Ri and said remaining portion Z as aligned in (d) to obtain a number Rq; and PA1 (g) taking said number Rq as a residue R of said number M when said number Rq has not more than q digits, and otherwise repeating steps (b) to (g) with said number Rq replacing said number M. PA1 shift register means for temporarily holding said number M; PA1 memory means for storing precomputed s-digit residues of at most k*a.sup.b/k different numbers with respect to said modulus N, where s, b and k are predetermined numbers; PA1 latch means for partitioning said number M in a shift register means into a block X of b digits obtained by separating b most significant digits of said number M, and a remaining portion Z of (q-b) digits, where b is a number equal to s times k; PA1 means for partitioning said block X into k sub-blocks Xi(i=1, . . . , k), each of s digits; PA1 means for finding residues Ri corresponding to said sub-blocks Xi with respect to said modulus N by looking in said memory means; PA1 means for aligning least significant digits of said residues Ri with a q-th most significant digit of said remaining portion Z; PA1 adder means for obtaining a number Rq by adding said residues Ri and said remaining portion Z as aligned by said aligning means; PA1 means for taking said number Rq as a residue R of said number M when said number Rq has not more than q digits; and PA1 means for replacing said number M in said shift register means by said number Rq when said number Rq has more than q digits.
where M and C denote a plaintext and a ciphertext, respectively, and e, d, and n are key informations. These computations are called the modulo-exponentiation.
To ensure the security of this cryptosystem, it is said that the keys n and d should be positive integers of two hundred decimal digits or more. However, as the key n becomes larger, an amount of computation will be increased.
The modulo exponentiation is always executed as a sequence of multiplication and modulo reduction so that the most time consuming portion of the modulo exponentiation is the computation of: EQU R=M1.times.M2 mod n.
To compute this at a high speed using a table look up technique, there is a conventional method which will be explained with reference to FIG. 1.
The conventional method shown in the FIG. 1 computes a residue of a number M(=M1.times.M2) with respect to a modulus n at a high speed. A portion of the number M which is larger than the modulus n is divided into blocks r1, r2 and r3 each of several bits.
Residues of the blocks r1, r2 and r3 with respect to the modulus n are stored in advance in residue tables RAM1, RAM2 and RAM3, respectively. Therefore, residues R1, R2 and R3 corresponding to the blocks r1, r2 and r3 are read out of the tables RAM1, RAM2 and RAM3 and added to Z.sub.1 which is a portion of the number M smaller than the modulus n, to reduce the number M. This operation is repeated until a residue of the number M is found.
The details of this technique is reported in "A Study on RSA parallel processing method" in "The Proceedings of the 1986 Work Shop on Cryptography and Information Security" by Naoya Torii, Mitsuhiro Higashi and Ryota Akiyama.
This conventional technique reduces M(=M1.times.M2) by using the residue tables to execute the residue computation at a high speed. However, it has a drawback that the residue tables must have enormous capacities. Supposing the key n is 512 bits and a dividend 1024 bits, when the upper 512 bits of the dividend are divided into blocks, each of several bits, and residue tables should be prepared for these blocks. If the length of one block is four bits, the number of blocks will be 128 so that 128 residue tables need to be prepared. As a result, the residue tables may require a memory of one mega bit or more.
If the length of each block is decreased, the residue tables may require less memory, but a computation speed will be reduced. Further, if the size of each residue table is large, it is cumbersome to rearrange the table when the modulus n is changed.
There is another conventional method to obtain a residue at a high speed. This method uses a multiplication table to efficiently solve division problems. For example, a multiplication table for modulo-2.sup.k numbers is prepared with respect to divisions by the modulo-2.sup.k numbers to find residues. This method is disclosed in Japanese Patent Application Laid Open No. S62-11937.
According to this method, a time necessary for the computation of a residue is substantially inverse proportion to the parameter k. Therefore, a processing speed may be increased by increasing the parameter k. However, the size of the multiplication table is substantially increased in proportion to 2.sup.k. Namely, the size of the multiplication table is exponentially increased as the parameter k increases. However, due to hardware limitations, the parameter k cannot drastically be enlarged to increase the processing speed.
As described in the above, according to the conventional residue computing systems, residues of respective digits of numbers whose residues are to be found need to be stored in advance in memories. Therefore, the capacity of each memory needs to be increased considerably as each number which is subjected to the residue computation becomes large, thus increasing the size and cost of hardware.